package MonotonicStack;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * 739.每日温度
 * 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer
 * 其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
 *
 * 如果求一个元素右边第一个更大元素，单调栈就是递增的，如果求一个元素右边第一个更小元素，单调栈就是递减的。
 */
public class dailyTemperatures {
    /**
     * 一刷
     */
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> stack = new Stack<>();
        int[] result = new int[temperatures.length];
        stack.push(0);
        for (int i = 1; i < temperatures.length; i++) {
            if (temperatures[i] <= temperatures[stack.peek()]) {
                stack.push(i);
            } else {
                while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
                    result[stack.peek()] = i - stack.peek();
                    stack.pop();
                }
                stack.push(i);
            }
        }
        return result;
    }

    /**
     * 二刷
     */
    //详细版本
    public int[] dailyTemperatures1(int[] temperatures) {
        int[] res = new int[temperatures.length];
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for (int i = 1; i < temperatures.length; i++) {
            if (!stack.isEmpty()) {
                if (temperatures[i] <= temperatures[stack.peek()]) {
                    stack.push(i);
                } else {
                    while (!stack.empty() && temperatures[i] > temperatures[stack.peek()]) {
                        int index = stack.pop();
                        res[index] = i - index;
                    }
                    stack.push(i);
                }
            } else {
                stack.push(i);
            }
        }
        return res;
    }

    //优化版本
    public int[] dailyTemperatures2(int[] temperatures) {
        int[] res = new int[temperatures.length];
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0);
        for (int i = 1; i < temperatures.length; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int index = stack.pop();
                res[index] = i - index;
            }
            stack.push(i);
        }
        return res;
    }
}
